package me.eg.fifth;

/**
 * 875. 爱吃香蕉的珂珂
 * <p>
 * 珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
 * <p>
 * 珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。  
 * <p>
 * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 * <p>
 * 返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
 * <p>
 * 链接：https://leetcode-cn.com/problems/koko-eating-bananas
 */
public class MinEatingSpeed {
    /**
     * 解法一：二分答案
     * 时间复杂度：O(NlogN)
     * 空间复杂度：O(1)
     *
     * 同样将求解问题转换为判定问题
     * 值域：[1, Max(nums)]
     * 解空间有单调性：小于答案，方案都不可行(等价于false)；大于等于答案，方案可行(等价于true)
     * 因此可以用二分查找在值域中寻找答案
     *
     * @param piles
     * @param h
     * @return
     */
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1, right = 0;
        for (int pile : piles) {
            right = Math.max(right, pile);
        }
        while (left < right) {
            int mid = (left + right) >> 1;
            if (canFinish(piles, h, mid)) right = mid;
            else left = mid + 1;
        }
        return right;
    }

    private boolean canFinish(int[] piles, int h, int speed) {
        int consumeHour = 0;
        for (int pile : piles) {
            consumeHour += (pile - 1) / speed + 1;
        }
        return consumeHour <= h;
    }
}
